package com.g02.by;

import com.g02.qt.ListNode;

public class ReverseNode {
    static ListNode headInsert(ListNode head, int left, int right) {
        // 采用头插法
        ListNode newHead = new ListNode(-1, head);
        ListNode prev = newHead;
        ListNode cur;
        for (int i = 0; i < left - 1; i++) {
            prev = prev.next;
        }
        cur = prev.next;
        ListNode end = cur;
        // 开始反转
        for (int i = 0; i <= right - left; i++) {
            ListNode nx =  cur.next;
            cur.next = prev.next;
            prev.next = cur;
            cur = nx;
        }
        end.next = cur;
        return newHead.next;
    }

    static ListNode chuanZheng(ListNode head, int left, int right) {
        // 使用穿针引线法
        ListNode newHead = new ListNode(-1, head);
        ListNode prev = newHead;
        for (int i = 0; i < left - 1; i++) {
            prev = prev.next;
        }
        ListNode p1 = prev.next;
        ListNode p2 = p1;
        for (int i = 0; i < right - left; i++) {
            p2 = p2.next;
        }
        ListNode end = p2.next;
        // 现在 p1 到 p2 之间就是要反转的节点，用无头节点的自反转的方法
        ListNode t1 = null;
        ListNode t2 = p1;
        while (t2 != end) {
            ListNode nx = t2.next;
            t2.next = t1;
            t1 = t2;
            t2 = nx;
        }
        prev.next = p2;
        p1.next = end;
        return  newHead.next;
    }
}
